package main

import "sync"

func main() {

}

type Entry struct {
	key   int
	value interface{}
	prev  *Entry
	next  *Entry
	l     *list
}

type list struct {
	root *Entry
}

type LRUCache struct {
	cache    map[int]*Entry
	ll       *list
	capacity int
	sync.Mutex
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		cache:    make(map[int]*Entry, capacity),
		ll:       &list{root: &Entry{}},
		capacity: capacity,
	}
}

func (ll *list) moveToFront(e *Entry) {
	if e.l != ll || ll.root.next == e {
		return
	}
	if e == ll.root {
		return
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = ll.root
	e.next = ll.root.next
	e.prev.next = e
	e.next.prev = e
}

func (this *LRUCache) Get(key int) int {
	// 先看缓存中是否存在
	if e, ok := this.cache[key]; ok {
		val := e.value.(int)
		// 移动当前entry到头部
		this.ll.moveToFront(e)
		return val
	}
	// 不存在，则返回-1
	return -1
}

func (ll *list) lazyInit() {
	if ll.root.next == nil {
		ll.root.next = ll.root
		ll.root.prev = ll.root
	}
}
func (ll *list) pushToFront(e *Entry) *Entry {
	ll.lazyInit()
	e.prev = ll.root
	e.next = ll.root.next
	e.prev.next = e
	e.next.prev = e
	e.l = ll
	return e
}

func (ll *list) back() *Entry {
	return ll.root.prev
}

func (this *LRUCache) removeOld() {
	this.Lock()
	e := this.ll.back()
	if e != nil {
		delete(this.cache, e.key)
		e.prev.next = e.next
		e.next.prev = e.prev
		e.prev = nil
		e.next = nil
		e.l = nil
		e = nil
	}
	this.capacity++
	this.Unlock()
}

func (this *LRUCache) Put(key int, value int) {
	// 先看缓存中是否存在
	this.Lock()
	val := this.Get(key)
	if val != -1 {
		e := this.cache[key]
		e.key = key
		e.value = value
	} else {
		// 不存在则是新增
		this.cache[key] = this.ll.pushToFront(&Entry{key: key, value: value})
		this.capacity--
	}
	this.Unlock()
	if this.capacity < 0 {
		this.removeOld()
	}
}
